package 路径总和;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 路径总和
 * @date 2022/11/4 12:12
 */
public class Demo112 {


    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(5);
        treeNode.left=new TreeNode(4);
        treeNode.right=new TreeNode(8);
        treeNode.right.right=new TreeNode(4);
        treeNode.right.left=new TreeNode(13);
        treeNode.left.left=new TreeNode(11);
        treeNode.left.left.left=new TreeNode(7);
        treeNode.left.left.right=new TreeNode(2);
        treeNode.right.right.right=new TreeNode(1);
        //结果集
        boolean b = hasPathSum(treeNode, 22);
        System.out.println(b);

    }

     //Definition for a binary tree node.
     public static class TreeNode {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode() {}
         TreeNode(int val) { this.val = val; }
         TreeNode(int val, TreeNode left, TreeNode right) {
             this.val = val;
             this.left = left;
             this.right = right;
         }
     }

    public static boolean hasPathSum(TreeNode root, int targetSum) {
          if(root==null){
              return false;
          }
        //结果集
        List<List<Integer>> res= new ArrayList<>();
        //单条路径
        List<Integer> path =new ArrayList<>();
        trackBack(root, path,res);
        for (int i = 0; i < res.size(); i++) {
            int sum = res.get(i).stream().mapToInt(s -> s).sum();
            if(sum==targetSum){
                return true;
            }
        }
        return false;
    }

    private static void trackBack(TreeNode root, List<Integer> path, List<List<Integer>> res) {
         path.add(root.val);
         if (root.left==null&&root.right==null){
             //不能直接添加path
             ArrayList temp=new ArrayList(path);
             res.add(temp);
             return;
         }
        if(root.left!=null){
            trackBack(root.left, path, res);
            //回溯
            path.remove(path.size()-1);
        }
        if(root.right!=null){
            trackBack(root.right, path, res);
            //回溯
            path.remove(path.size()-1);
        }

    }

}
